package dp;

/**
 * @author Liaorun
 */
public class MinScoreTriangulation {

    /**
     * @param values
     * @return
     */
    public static int minScoreTriangulation(int[] values) {

        int[][] dp = new int[values.length][values.length];

        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length; j++) {
                dp[i][j] = -1;
            }
        }

        return f(values, 0, values.length - 1, dp);
    }

    private static int f(int[] values, int i, int j, int[][] dp) {
        if (i >= j - 1) {
            // 不够3个点，不会有得分
            return 0;
        }

        if (dp[i][j] != -1) {
            // 缓存的答案
            // 如果命中直接返回
            return dp[i][j];
        }

        int ans = Integer.MAX_VALUE;

        for (int m = i + 1; m < j; m++) {
            ans = Math.min(ans, f(values, i, m, dp) + f(values, m, j, dp) + values[i]);
        }

        dp[i][j] = ans;

        return ans;
    }

    public static int minS(int[] arr, int l, int r) {
        if (l > r - 2) {
            // 没有3个点，凑不齐3角形，返回0个点
            return 0;
        } else {
            int ans = Integer.MAX_VALUE;

            for (int m = l + 1; m < r; m++) {
                int left = minS(arr, l, m);
                int mid = arr[l] * arr[m] * arr[r];
                int right = minS(arr, m, r);
                int curAns = left + mid + right;
                ans = Math.min(curAns, ans);
            }

            return ans;
        }
    }


}
